package my.jwds.p101;

import my.jwds.p94.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class IsSymmetric {

    public static void main(String[] args) {
        IsSymmetric o = new IsSymmetric();
        TreeNode node = TreeNode.to_binaryHaveNull(new Integer[]{1,2,2});
        System.out.println(o.isSymmetric(node));
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null)return true;
        TreeNode[] list = new TreeNode[2];
        list[0] = root.left;
        list[1] = root.right;
        return nextSymmetry(list);
    }

    public boolean nextSymmetry(TreeNode[] list){

        boolean nextNonNullFlag = false;
        int size = list.length;
        if (size%2 ==1)return false;
        TreeNode[] next = new TreeNode[size*2];
        int half = size /2;
        for (int i = 0; i < half; i++) {
            TreeNode node1 = list[i];
            TreeNode node2 = list[size-i-1];
            if (node1 != null && node2 != null){
                if (node1.val != node2.val)return false;
                if (!nextNonNullFlag && (node1.left!= null || node1.right != null || node2.left!=null || node2.right != null))nextNonNullFlag = true;
                next[2*i] = node1.left;
                next[2*i+1] = node1.right;
                next[2*(size-i-1)] = node2.left;
                next[2*(size-i-1)+1] = node2.right;
            }else if (node1 != null || node2 != null){
                return false;
            }

        }

        if (nextNonNullFlag)return nextSymmetry(next);
        return true;
    }

    public boolean isSymmetric_rec(TreeNode root) {
        return check(root.right,root.left);
    }

    public boolean check(TreeNode node1, TreeNode node2){
        if (node1 == null && node2 == null){
            return true;
        }
        if (node1 == null || node2 == null){
            return false;
        }
        return node1.val == node2.val && check(node1.left,node2.right) && check(node1.right,node2.left);
    }

}
